1. Field of the Invention
The capacity of devices such as computers and transmission lines has long been shared among a set of users by time multiplexing such devices among the users. When the device is time multiplexed, each user receives use of the device for a relatively short interval of time in turn. A user continues to receive use for intervals of time in turn until the task he wishes the device to perform for him is finished. Various techniques have been developed for such time multiplexing. Goals of such techniques typically include the following:
Efficient use of the device; PA1 Provision of priorities for use of the device among the users; PA1 Providing for a fair allocation of the use of the device among the users; PA1 Protecting other users from a malicious or malfunctioning user. PA1 Guaranteeing the rate of service and the amount of delay between accesses. Achieving these goals has become more difficult as the capacities of the devices have increased and the range of needs of the users has broadened. For example, users of a single time-multiplexed data transmission line may be simultaneously employing the line to carry information ranging from digitized video signals through digitized voice signals to interactive commands to and responses from a computer program to file transfers to electronic mail.
2. Description of the Prior Art
One useful technique for multiplexing is the round-robin server. A block diagram of such a server is shown in FIG. 1. Round-robin server 101 provides the use of time multiplexed resource 103 to a number of entities. For example, if time multiplexed resource 103 is a computer, the entities may be processes running on the computer; if it is a transmission line, the entities may be virtual circuits which are using the transmission line. Whenever an entity has work for resource 103 to do, there is a single entry 113 for the entity on work list 111. Work list 111 is a queue with a head and tail. If an entity has work for resource 103 to do and there is presently no entry 113 for the entity on work list 111, an entry for the entity is placed at the tail of work list 111.
Provider 105 multiplexes resource 103 among the entities by reading from the head of work list 111. It takes the entry 113 currently at the head of work list 111 and provides the entity specified in entry 113 with a fixed amount of time on resource 103. When the time is expired, Provider 105 determines whether there is more work to do for the entity. If there is, the entry 113 is returned to the tail of work list 111; if not, it is removed from list 111. The above steps are repeated for each entry 113 on the list. If work 111 is empty, resource 103 simply idles.
Since every entity using the resource has only a single entry on work list 111 and each entry represents a fixed quantity of access to resource 103, round-robin server 101 can guarantee a minimum level of service: if there are n entities being served by server 101, each entity will receive at least 1/n of the total access to resource 103 and the time between accesses by the entity will be at most EQU n*(the interval of time given each entity)
Round robin server 101 can, however, make no guarantees regarding any level of service above the minimum level, even though entities will on the average receive more and more frequent access. The reason for this is that actual access above the guaranteed minimum for a given entity is a function of the amount of access required by the other entities.
An example of an area in which a round-robin server like that of FIG. 1 is not adequate is a broadband integrated services digital network (ISDN). Such a network carries many classes of traffic, including digitized video and audio and computer traffic. Broadband ISDN transfers data using a technique called asynchronous transfer mode (ATM). In ATM, all data is transferred in cells. A cell has a header, containing information which the network requires to deliver the cell to its destination via a virtual circuit, and a body containing the data to be transferred via the virtual circuit. FIG. 2 shows a cell 201 as defined for use in ATM networks. Cell 201 is 53 bytes long; 48 of the bytes are body 205; the remaining five bytes are header 203.
While all data in a broadband ISDN moves in cells, the kind of data being carried in the cell 201 necessarily influences the manner in which the cell is dealt with by the ISDN. Different classes of data have different requirements as regards bandwidth (the amount of data carried over a given period time) and delay (the time interval between the arrival of a first part of the data and a related second part). For example, real-time video traffic requires high bandwidth with low variability in delay. Voice traffic requires low variability in delay but does not need high bandwidth. Computer traffic spans a wide range of requirements, from interactive graphics applications which have bandwidth and delay requirements approaching those of real-time video traffic applications, through interactive character-based applications which require low delay but do not need high bandwidth, to applications such as electronic mail which need neither low delay nor high bandwidth.
As explained above, round-robin server 101 can guarantee only minimum access rates and maximum intervals between accesses. Moreover, all entities served by round-robin server 101 have the same minimum access rates and maximum intervals. For these reasons, round-robin server 101 cannot be easily and economically employed in network applications which must deal with traffic moving at different average rates. It is an object of the invention described below to provide apparatus and methods for multiplexing resource 103 among a set of entities at controlled average rates.